/*****************************************************************************
 *  ENTROPY - emerging network to reduce orwellian potency yield
 *
 *  Copyright (C) 2002 Juergen Buchmueller <pullmoll@stop1984.com>
 *
 *  This program is free software; you can redistribute it and/or modify
 *  it under the terms of the GNU General Public License as published by
 *  the Free Software Foundation; either version 2 of the License, or
 *  (at your option) any later version.
 *
 *  This program is distributed in the hope that it will be useful,
 *  but WITHOUT ANY WARRANTY; without even the implied warranty of
 *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 *  GNU General Public License for more details.
 *
 *  You should have received a copy of the GNU General Public License
 *  along with this program; if not, write to the Free Software Foundation,
 *  Inc., 51 Franklin Street, Fifth Floor, Boston, MA  02110-1301, USA
 *
 *	$Id: shmalloc.c,v 1.4 2005/07/12 23:12:29 pullmoll Exp $
 *****************************************************************************/
#include "osd.h"
#include "config.h"
#include "memalloc.h"
#include "shmalloc.h"
#include "logger.h"

#if	SHM_DEBUG
#undef	NDEBUG
#include "tools.h"
#define	assert(e) if(!(e)){LOGS(L_SHM,L_ERROR,("assert:"#e "\n"));}
#else
#define	NDEBUG
#define	assert(e)
#endif

#if	HAVE_MMAP == 0
int g_shm_key = -1;
int g_shm_id = -1;
#endif	/* HAVE_MMAP == 0 */
shm_pool_t *g_shm = NULL;

#define	LOCK() osd_sem_wait(&g_shm->sem)
#define	UNLOCK() osd_sem_post(&g_shm->sem)

#undef	OBLITERATE
#undef	DISPLAY
#undef	BOUNDS
#undef	ZERO_ERROR
#undef	NULL_ERROR
#undef	INVALID_ERROR
#define	BESTFIT

#undef	FIT
#ifdef	BESTFIT
#define	FIT(x)	bestfit(x FILE_LINE_PARMS)
#else	/* BESTFIT */
#define	FIT(x)	firstfit(x FILE_LINE_PARMS)
#endif	/* !BESTFIT */

#undef	PATTERN
#define	PATTERN(p)	((char)((uint32_t)(p) & 0xff))
#undef	MIN
#define	MIN(x,y)	((x) < (y) ? (x) : (y))
#undef	MAX
#define	MAX(x,y)	((x) > (y) ? (x) : (y))
#undef	ALIGN
#define	ALIGN(p)	(((p) + (sizeof(align_t) - 1)) & ~(sizeof(align_t) - 1))

#undef	ADDR
#undef	AFTER
#undef	OVERHEAD

#ifdef	BOUNDS
#define	ADDR(n)		((caddr_t)(n) + sizeof(shm_node_t) + sizeof(align_t))
#define	AFTER(n)	(ADDR(n) + (n)->x.rsize + sizeof(align_t))
#define	OVERHEAD	(sizeof(shm_node_t) + (2 * sizeof(align_t)))
#else
#define	ADDR(n)		((caddr_t)(n) + sizeof(shm_node_t))
#define	AFTER(n)	(ADDR(n) + (n)->x.rsize)
#define	OVERHEAD	(sizeof(shm_node_t))
#endif	/* BOUNDS */

#undef	STATUS
#ifdef	DISPLAY
#define	STATUS(s) \
	LOGS(L_SHM,L_MINOR,("%8d %05u/%04u %4.1f%% (%7s) <%8s:%-5d>\n", \
		g_shm->total, \
		(unsigned)g_shm->alloc_len, \
		(unsigned)g_shm->avail_len, \
		(g_shm->avail_len + g_shm->alloc_len) ? \
			g_shm->avail_len*99.9 / (g_shm->avail_len+g_shm->alloc_len):0.0, \
		(s), \
		((file) ? (file) : "unknown"), \
		((line) ? (line) : 0)))
#else
#define	STATUS(s)
#endif

#undef	MINNODE
#define	MINNODE	(64 * sizeof(align_t))

#undef	ADJACENT
#define	ADJACENT(n1,n2) \
		((caddr_t)(n1) + OVERHEAD + (n1)->x.rsize == (caddr_t)(n2))

typedef	double align_t;

typedef union shm_node_u {
	struct {
		size_t rsize;	/* real size */
		size_t usize;	/* user size */
		pid_t pid;		/* process ID of the allocating process */
#if	SHM_DEBUG
		char *file;
		uint32_t line;
#endif
		union shm_node_u *next;
	} x;
	align_t align;
}	shm_node_t;

typedef enum list_e {
	AVAILABLE,
	ALLOCATED
}	list_t;

#undef	PAGESIZE
#define	PAGESIZE	1024

/* put a breakpoint here for debugging */
static void debug() {
	g_shm->total = g_shm->total;
}

#if	SHM_DEBUG
static char *at_file_line(char *file, uint32_t line)
{
	static char buff[4][80];
	static int which = 0;

	which = (which + 1) % 4;
	if (NULL == file) {
		buff[which][0] = '\0';
	} else {
		pm_snprintf(buff[which], sizeof(buff[which]), " at %s:%d", file, line);
	}
	return buff[which];
}
#endif

#ifdef	BOUNDS
static void pnode(shm_node_t *n)
{
	FUN("pnode");
#if	SHM_DEBUG
	LOGS(L_SHM,L_ERROR,
		("%#x: rsize=%#x usize=%#x addr=%#x pid=%u file=%s:%u next=0x%x\n",
		(unsigned)n, (unsigned)n->x.rsize, (unsigned)n->x.usize,
		(unsigned)ADDR(n), (unsigned)n->x.pid, (unsigned)n->x.next,
		(char *)((NULL != n->x.file) ? n->x.file : "unknown"),
		(unsigned)n->x.line));
#else
	LOGS(L_SHM,L_ERROR,
		("%#x: rsize=%#x usize=%#x addr=%#x pid=%u next=0x%x\n",
		(unsigned)n, (unsigned)n->x.rsize, (unsigned)n->x.usize,
		(unsigned)ADDR(n), (unsigned)n->x.pid, (unsigned)n->x.next));
#endif
}
#endif

#if	0
static void plist(shm_node_t *head)
{
	shm_node_t *c;
	FUN("plist");

	LOGS(L_SHM,L_ERROR,("=== list starts at 0x%x ===\n",
		(uint32_t)head));
	c = head;
	while (NULL != c) {
		pnode(c);
		c = c->x.next;
	}
}
#endif

#ifndef	NDEBUG
static uint32_t llength(shm_node_t *head)
{
	uint32_t i = 0;
	shm_node_t *curr = head;
	while (NULL != curr) {
		i++;
		curr = curr->x.next;
	}
	return i;
}
#endif

static void delete(list_t l, shm_node_t *node)
{
	shm_node_t *curr, *prev, **head;
	FUN("delete");

	assert(ALLOCATED == l || AVAILABLE == l);
	assert(NULL != node);
	head = (shm_node_t **)((l == ALLOCATED) ?
		&g_shm->allocated : &g_shm->available);
	assert(NULL != *head);

	assert(g_shm->alloc_len == llength(g_shm->allocated));
	assert(g_shm->avail_len == llength(g_shm->available));

	curr = prev = *head;
	while (NULL != curr && ADDR(curr) > ADDR(node)) {
		prev = curr;
		curr = curr->x.next;
	}

	assert(NULL != curr);

	if (ALLOCATED == l) {
		g_shm->alloc_len -= 1;
	} else {
		g_shm->avail_len -= 1;
	}

	if (curr == prev) {
		*head = curr->x.next;
	} else {
		prev->x.next = curr->x.next;
	}
}	/* delete */


static void insert(list_t l, shm_node_t *node)
{
	shm_node_t *curr, *prev, **head;
	FUN("insert");

	assert(ALLOCATED == l || AVAILABLE == l);
	assert(NULL != node);
	head = (shm_node_t **)((ALLOCATED == l) ?
		&g_shm->allocated : &g_shm->available);

	assert(g_shm->alloc_len == llength(g_shm->allocated));
	assert(g_shm->avail_len == llength(g_shm->available));

	curr = prev = *head;
	while (NULL != curr && ADDR(curr) > ADDR(node)) {
		prev = curr;
		curr = curr->x.next;
	}

	assert(NULL == curr || ADDR(curr) != ADDR(node));

	if (AVAILABLE == l &&
		NULL != *head &&
		NULL != curr &&
		ADJACENT(curr,node)) {
		curr->x.rsize += OVERHEAD + node->x.rsize;
		if (ADJACENT(curr,prev)) {
			delete(AVAILABLE, prev);
			curr->x.rsize += OVERHEAD + prev->x.rsize;
		}
	} else {
		if (ALLOCATED == l) {
			g_shm->alloc_len += 1;
		} else {
			g_shm->avail_len += 1;
		}
		node->x.next = curr;
		if (curr == prev) {
			*head = node;
		} else {
			prev->x.next = node;
			if (AVAILABLE == l && NULL != *head && ADJACENT(node,prev)) {
				delete(AVAILABLE, prev);
				node->x.rsize += OVERHEAD + prev->x.rsize;
			}
		}
	}
}	/* insert */

#ifdef	BOUNDS
static void fillbounds(shm_node_t *node)
{
	char *start;
	char pattern = PATTERN(node);
	int length, i;

	start = (char *)node + sizeof(shm_node_t);
	length = sizeof(align_t);
	for (i = 0; i < length; i++) {
		start[i] = pattern;
	}

	start = (char *)node + sizeof(shm_node_t) + sizeof(align_t) + node->x.usize;
	length = node->x.rsize - node->x.usize + sizeof(align_t);
	for (i = 0; i < length; i++) {
		start[i] = pattern;
	}
}	/* fillbounds */

static void checkbounds(shm_node_t *node, char *func)
{
	int i, start, end;
	unsigned char pattern = PATTERN(node);
	unsigned char current;
	FUN("checkbounds");

#define	CHECK(i) \
		current = ADDR(node)[(i)]; \
		if (current != pattern) { \
			LOGS(L_SHM,L_ERROR, \
				("\n%s: found '\\%03o`instead of '\\%03o' at 0x%x[%d]\n", \
				func, current, pattern, (uint32_t)ADDR(node), (i))); \
			pnode(node); \
			debug(); \
		}

	start = -sizeof(align_t);
	end = 0;
	for (i = start; i < end; i++) {
		CHECK(i);
	}

	start = node->x.usize;
	end = node->x.rsize + sizeof(align_t);
	for (i = start; i < end; i++) {
		CHECK(i);
	}
}	/* checkbounds */

static void lbounds(shm_node_t *head)
{
	shm_node_t *curr = head;
	while (NULL != curr) {
		checkbounds(curr, "lbounds");
		curr = curr->x.next;
	}
}	/* lbounds */
#endif

static shm_node_t *find(shm_node_t *head, caddr_t ptr)
{
	shm_node_t *curr = head;

	while (NULL != curr && ADDR(curr) > ptr) {
		curr = curr->x.next;
	}

	if (NULL == curr || ADDR(curr) != ptr) {
		return NULL;
	}

	return curr;
}	/* find */

static shm_node_t *expand(size_t size FILE_LINE_ARGS)
{
	shm_node_t *node = NULL;
	size_t i, big;
	FUN("expand");

#ifdef	BOUNDS
	lbounds(g_shm->allocated);
#endif
	big = MAX((8 * PAGESIZE), (((size + OVERHEAD) / PAGESIZE) + 1) * PAGESIZE);
	assert(big >= size + OVERHEAD);

	/* find a pool where 'big' fits into */
	for (i = 0; i < g_shm->pool_cnt; i++) {
		if (g_shm->brk[i] + big <= g_shm->max[i]) {
			node = (shm_node_t *)&g_shm->pool[i][g_shm->brk[i]];
			g_shm->brk[i] = g_shm->brk[i] + big;
			break;
		}
	}
	/* no pool found: we're lost */
	if (i == g_shm->pool_cnt) {
		LOGS(L_SHM,L_ERROR,("expand: setting break +%llu failed\n",
			(uint64_t)big));
		for (i = 0; i < g_shm->pool_cnt; i++) {
			LOGS(L_SHM,L_ERROR,("pool[%d] %#llx/%#llx\n",
				(int)i, (uint64_t)g_shm->brk[i], (uint64_t)g_shm->max[i]));
		}
		return NULL;
	}

	node->x.rsize = big - OVERHEAD;
	node->x.next = NULL;
	node->x.pid = getpid();
#if	SHM_DEBUG
	node->x.file = file;
	node->x.line = line;
#endif

	return node;
}	/* expand */

#ifndef	BESTFIT
static shm_node_t *firstfit(size_t size FILE_LINE_ARGS)
{
	shm_node_t *curr;
	size_t aligned = ALIGN(size);
	FUN("firstfit");

#ifdef	ZERO_ERROR
	assert(0 != size);
#endif	/* ZERO_ERROR */

	curr = g_shm->available;
	while (NULL != curr && curr->x.rsize < aligned) {
		curr = curr->x.next;
	}

	if (NULL == curr) {
		if (NULL == (curr = expand(aligned FILE_LINE_PARMS))) {
			return NULL;
		}
	} else {
		assert(NULL == find(g_shm->allocated, ADDR(curr)));
		assert(curr == find(g_shm->available, ADDR(curr)));

		delete(AVAILABLE, curr);
	}

	assert(NULL == find(g_shm->allocated, ADDR(curr)));
	assert(NULL == find(g_shm->available, ADDR(curr)));

	if (curr->x.rsize >= aligned + OVERHEAD + MINNODE) {
		shm_node_t *node;
		size_t leftover;

		leftover = curr->x.rsize - aligned - OVERHEAD;
		curr->x.rsize = aligned;

		node = (shm_node_t *)AFTER(curr);
		node->x.rsize = leftover;

		assert(NULL == find(g_shm->allocated, ADDR(node)));
		assert(NULL == find(g_shm->available, ADDR(node)));

		insert(AVAILABLE, node);

		assert(NULL == find(g_shm->allocated, ADDR(node)));
		assert(node == find(g_shm->available, ADDR(node)));
	}

	curr->x.usize = size;

#ifdef	BOUNDS
	fillbounds(curr);
#endif	/* BOUNDS */

	insert(ALLOCATED, curr);

	assert(curr == find(g_shm->allocated, ADDR(curr)));
	assert(NULL == find(g_shm->available, ADDR(curr)));

	return curr;
}	/* firstfit */

#else	/* BESTFIT */

static shm_node_t *bestfit(size_t size FILE_LINE_ARGS)
{
	shm_node_t *curr, *best;
	size_t aligned = ALIGN(size);
	size_t over, bestover = (size_t)0x7fffffff;
	FUN("bestfit");

#if	SHM_DEBUG
	(void)file;
	(void)line;
#endif

#ifdef	ZERO_ERROR
	assert(0 != size);
#endif	/* ZERO_ERROR */

	best = NULL;
	curr = g_shm->available;
	while (NULL != curr) {
		if (curr->x.rsize >= size) {
			over = curr->x.rsize - size;
			if (over < bestover || curr == g_shm->available) {
				bestover = over;
				best = curr;
			}
		}
		curr = curr->x.next;
	}

	if (NULL == best) {
		if (NULL == (best = expand(aligned FILE_LINE_PARMS))) {
			return NULL;
		}
	} else {
		assert(NULL == find(g_shm->allocated, ADDR(best)));
		assert(best == find(g_shm->available, ADDR(best)));

		delete(AVAILABLE, best);
	}

	assert(NULL == find(g_shm->allocated, ADDR(best)));
	assert(NULL == find(g_shm->available, ADDR(best)));

	if (best->x.rsize >= aligned + OVERHEAD + MINNODE) {
		shm_node_t *node;
		size_t leftover;

		leftover = best->x.rsize - aligned - OVERHEAD;
		best->x.rsize = aligned;

		node = (shm_node_t *)AFTER(best);
		node->x.rsize = leftover;

		assert(NULL == find(g_shm->allocated, ADDR(node)));
		assert(NULL == find(g_shm->available, ADDR(node)));

		insert(AVAILABLE, node);

		assert(NULL == find(g_shm->allocated, ADDR(node)));
		assert(node == find(g_shm->available, ADDR(node)));
	}

	best->x.usize = size;

#ifdef	BOUNDS
	fillbounds(best);
#endif	/* BOUNDS */

	insert(ALLOCATED, best);

	assert(best == find(g_shm->allocated, ADDR(best)));
	assert(NULL == find(g_shm->available, ADDR(best)));

	return best;
}

#endif

/* ------------------------------------------------------- */

/* ARGUSED */
caddr_t shm_malloc(size_t size FILE_LINE_ARGS)
{
	shm_node_t *store;
	FUN("shm_malloc");

	LOGS(L_SHM,L_DEBUGX,("shm_malloc(%d)%s\n",
		(int)size, AT_FILE_LINE));
	if (0 != LOCK()) {
		LOGS(L_SHM,L_DEBUG,("lock failed%s\n",
			AT_FILE_LINE));
		return NULL;
	}
	if (0 == size) {
		LOGS(L_SHM,L_ERROR,("malloc: attempt to allocate 0 bytes%s\n",
			AT_FILE_LINE));
#ifdef	ZERO_ERROR
#if	SHM_DEBUG
		if (NULL != file && 0 != line)
			debug();
#endif
		UNLOCK();
		return NULL;
#endif	/* ZERO_ERROR */
	}

	store = FIT(size);

	if (NULL == store) {
		LOGS(L_SHM,L_ERROR,("malloc: unable to allocate %d bytes%s\n",
			(int)size, AT_FILE_LINE));
		debug();
		UNLOCK();
		return NULL;
	}

#ifdef	OBLITERATE
	memset(ADDR(store), '\001', size);
#endif	/* OBLITERATE */

	store->x.pid = getpid();
#if	SHM_DEBUG
	store->x.file = file;
	store->x.line = line;
#endif

	g_shm->total += size;
	STATUS("malloc");

	UNLOCK();
	return ADDR(store);
}	/* shm_malloc */

/* ARGUSED */
caddr_t shm_calloc(uint32_t num, size_t size FILE_LINE_ARGS)
{
	shm_node_t *store;
	uint32_t bytes;
	FUN("shm_calloc");

	LOGS(L_SHM,L_DEBUGX,("shm_calloc(%u,%d)%s\n",
		num, (int)size, AT_FILE_LINE));
	if (0 != LOCK()) {
		LOGS(L_SHM,L_DEBUG,("lock failed%s\n",
			AT_FILE_LINE));
		return NULL;
	}
	if (0 == num && 0 == size) {
		LOGS(L_SHM,L_ERROR,("calloc: attempt to allocate 0 items of size 0%s\n",
			AT_FILE_LINE));
#ifdef	ZERO_ERROR
#if	SHM_DEBUG
		if (NULL != file && 0 != line)
			debug();
#endif
		UNLOCK();
		return NULL;
#endif	/* ZERO_ERROR */
	}

	if (0 == num) {
		LOGS(L_SHM,L_ERROR,("calloc: attempt to allocate 0 items of size %d%s\n",
			(int)size, AT_FILE_LINE));
#ifdef	ZERO_ERROR
#if	SHM_DEBUG
		if (NULL != file && 0 != line)
			debug();
#endif
		UNLOCK();
		return NULL;
#endif	/* ZERO_ERROR */
	}

	if (0 == size) {
		LOGS(L_SHM,L_ERROR,("calloc: attempt to allocate %d items of size 0%s\n",
			num, AT_FILE_LINE));
#ifdef	ZERO_ERROR
#if	SHM_DEBUG
		if (NULL != file && 0 != line)
			debug();
#endif
		UNLOCK();
		return NULL;
#endif	/* ZERO_ERROR */
	}

	bytes = num * size;

	store = FIT(bytes);

	if (NULL == store) {
		LOGS(L_SHM,L_ERROR,("calloc: unable to allocate %d bytes%s\n",
			bytes, AT_FILE_LINE));
		debug();
		UNLOCK();
		return NULL;
	}

	memset(ADDR(store), '\000', bytes);
	store->x.pid = getpid();
#if	SHM_DEBUG
	store->x.file = file;
	store->x.line = line;
#endif

	g_shm->total += bytes;
	STATUS("calloc");

	UNLOCK();
	return ADDR(store);
}	/* _calloc */

/* ARGUSED */
caddr_t shm_realloc(caddr_t ptr, size_t size FILE_LINE_ARGS)
{
	shm_node_t *t;
	shm_node_t *store;
	FUN("shm_realloc");

	LOGS(L_SHM,L_DEBUGX,("shm_realloc(%p,%d)%s\n",
		ptr, (int)size, AT_FILE_LINE));
	if (NULL == ptr) {
		return shm_malloc(size FILE_LINE_PARMS);
	}

	if (0 != LOCK()) {
		LOGS(L_SHM,L_DEBUG,("lock failed%s\n",
			AT_FILE_LINE));
		return NULL;
	}
	t = find(g_shm->allocated, ptr);
	if (NULL == t) {
		LOGS(L_SHM,L_ERROR,("realloc: attempt to realloc unallocated memory (%p)%s\n",
			ptr, AT_FILE_LINE));
		debug();
		UNLOCK();
		return NULL;
	}

#ifdef	BOUNDS
	checkbounds(t, "realloc");
#endif	/* BOUNDS */

	g_shm->total += size - t->x.usize;
	STATUS("realloc");

	if (t->x.rsize >= size) {

#ifdef	OBLITERATE
		if (t->x.rsize != size) {
			memset(ADDR(t) + t->x.usize, '\001', size - t->x.usize);
		}
#endif	/* OBLITERATE */

		t->x.usize = size;
		t->x.pid = getpid();
#if	SHM_DEBUG
		t->x.file = file;
		t->x.line = line;
#endif

#ifdef	BOUNDS
		fillbounds(t);
#endif

		UNLOCK();
		return ADDR(t);
	}

	store = FIT(size);

	if (NULL == store) {
		LOGS(L_SHM,L_ERROR,("realloc: unable to allocate %d bytes%s\n",
			(int)size, AT_FILE_LINE));
		debug();
		return NULL;
	}

	memcpy(ADDR(store), ADDR(t), MIN(t->x.usize, size));

	assert(NULL == find(g_shm->available, ptr));
	assert(t == find(g_shm->allocated, ptr));

	delete(ALLOCATED, t);
	insert(AVAILABLE, t);

	assert(NULL == find(g_shm->allocated, ptr));
	/*
	 * collapsing prevents us from checking:
	 * assert(t == find(g_shm->available, ptr));
	 */

	store->x.pid = getpid();
#if	SHM_DEBUG
	store->x.file = file;
	store->x.line = line;
#endif

	STATUS("realloc");
	UNLOCK();
	return ADDR(store);
}	/* shm_realloc */

/* ARGUSED */
char *shm_strdup(const char *src FILE_LINE_ARGS)
{
	caddr_t ptr;
	size_t size;
	FUN("shm_strdup");

	if (NULL == src) {
		return NULL;
	}
	size = strlen(src) + 1;
	ptr = shm_calloc(size, sizeof(char) FILE_LINE_PARMS);
	if (NULL == ptr) {
		LOGS(L_SHM,L_ERROR,("strdup: unable to allocate %d bytes%s\n",
			(int)size, AT_FILE_LINE));
		debug();
		return NULL;
	}
	strncpy(ptr, src, size);
	return (char *)ptr;
}	/* shm_strdup */

/* ARGUSED */
void shm_free(caddr_t ptr FILE_LINE_ARGS)
{
	shm_node_t *t;
	FUN("shm_free");

	LOGS(L_SHM,L_DEBUGX,("shm_free(%x)%s\n",
		(uint32_t)ptr, AT_FILE_LINE));

#if	NULL_ERROR
	if (NULL == ptr) {
		LOGS(L_SHM,L_DEBUGX,("free: attempt to free NULL%s\n",
			AT_FILE_LINE));
#if	SHM_DEBUG
		if (NULL != file && 0 != line)
			debug();
#endif
		return;
	}
#else
	if (NULL == ptr) {
		return;
	}
#endif

#if	INVALID_ERROR
	if (INVALID_ADDR == ptr) {
		LOGS(L_SHM,L_DEBUGX,("free: attempt to free INVALID_ADDR%s\n",
			AT_FILE_LINE));
#if	SHM_DEBUG
		if (NULL != file && 0 != line)
			debug();
#endif
		return;
	}
#else
	if (INVALID_ADDR == ptr) {
		return;
	}
#endif

	if (0 != LOCK()) {
		LOGS(L_SHM,L_DEBUG,("lock failed%s\n",
			AT_FILE_LINE));
		return;
	}
	t = find(g_shm->allocated, ptr);

	if (NULL == t) {
		LOGS(L_SHM,L_ERROR,("free: attempt to free unallocated memory (%p)%s\n",
			ptr, AT_FILE_LINE));
#if	SHM_DEBUG
		if (NULL != file && 0 != line)
			debug();
#endif
		UNLOCK();
		return;
	}

#ifdef	BOUNDS
	checkbounds(t, "free");
#endif	/* BOUNDS */

	assert(t == find(g_shm->allocated, ptr));
	assert(NULL == find(g_shm->available, ptr));

	delete(ALLOCATED, t);
	insert(AVAILABLE, t);

	assert(NULL == find(g_shm->allocated, ptr));
	/*
	 * collapsing prevents us from checking:
	 * assert(t == find(g_shm->available, ptr));
	 */

#ifdef	OBLITERATE
	memset(ADDR(t), '\002', t->x.usize);
#else
	/* paranoid */
	memset(ADDR(t), '\000', t->x.usize);
#endif	/* OBLITERATE */

	g_shm->total -= t->x.usize;
	STATUS("free");
	UNLOCK();
}	/* shm_free */

/* ARGUSED */
int shm_valid(caddr_t ptr FILE_LINE_ARGS)
{
	shm_node_t *t;
	FUN("shm_valid");

	LOGS(L_SHM,L_DEBUGX,("shm_valid(%p)%s\n",
		ptr, AT_FILE_LINE));
#if	NULL_ERROR
	if (NULL == ptr) {
		LOGS(L_SHM,L_DEBUG,("free: attempt to validate NULL%s\n",
			AT_FILE_LINE));
#if	SHM_DEBUG
		if (NULL != file && 0 != line)
			debug();
#endif
		errno = EINVAL;
		return -1;
	}
#else
	if (NULL == ptr) {
		errno = EINVAL;
		return -1;
	}
#endif

#if	INVALID_ERROR
	if (INVALID_ADDR == ptr) {
		LOGS(L_SHM,L_DEBUG,("free: attempt to validate INVALID_ADDR%s\n",
			AT_FILE_LINE));
#if	SHM_DEBUG
		if (NULL != file && 0 != line)
			debug();
#endif
		errno = EINVAL;
		return -1;
	}
#else
	if (INVALID_ADDR == ptr) {
		errno = EINVAL;
		return -1;
	}
#endif

	if (0 != LOCK()) {
		LOGS(L_SHM,L_DEBUG,("lock failed%s\n",
			AT_FILE_LINE));
		errno = EINVAL;
		return -1;
	}
	t = find(g_shm->allocated, ptr);

	if (NULL == t) {
		LOGS(L_SHM,L_DEBUG,("invalid pointer (%p)%s\n",
			ptr, AT_FILE_LINE));
#if	SHM_DEBUG
		if (NULL != file && 0 != line)
			debug();
#endif
		UNLOCK();
		errno = EINVAL;
		return - 1;
	}

#ifdef	BOUNDS
	checkbounds(t, "valid");
#endif	/* BOUNDS */

	STATUS("valid");
	UNLOCK();
	return 0;
}	/* shm_valid */

int shm_pid_set(caddr_t ptr, pid_t pid FILE_LINE_ARGS)
{
	shm_node_t *t;
	FUN("shm_pid_set");

	LOGS(L_SHM,L_DEBUGX,("shm_pid_set(%p,%u)%s\n",
		ptr, (unsigned)pid, AT_FILE_LINE));

#if	NULL_ERROR
	if (NULL == ptr) {
		LOGS(L_SHM,L_DEBUG,("free: attempt to validate NULL%s\n",
			AT_FILE_LINE));
#if	SHM_DEBUG
		if (NULL != file && 0 != line)
			debug();
#endif
		errno = EINVAL;
		return -1;
	}
#else
	if (NULL == ptr) {
		errno = EINVAL;
		return -1;
	}
#endif

#if	INVALID_ERROR
	if (INVALID_ADDR == ptr) {
		LOGS(L_SHM,L_DEBUG,("free: attempt to validate INVALID_ADDR%s\n",
			AT_FILE_LINE));
#if	SHM_DEBUG
		if (NULL != file && 0 != line)
			debug();
#endif
		errno = EINVAL;
		return -1;
	}
#else
	if (INVALID_ADDR == ptr) {
		errno = EINVAL;
		return -1;
	}
#endif

	if (0 != LOCK()) {
		LOGS(L_SHM,L_DEBUG,("lock failed%s\n",
			AT_FILE_LINE));
		errno = EAGAIN;
		return -1;
	}

	t = find(g_shm->allocated, ptr);
	if (NULL == ptr) {
		LOGS(L_SHM,L_DEBUG,("pid_set: attempt to set PID for NULL%s\n",
			AT_FILE_LINE));
#if	SHM_DEBUG
		if (NULL != file && 0 != line)
			debug();
#endif
		UNLOCK();
		errno = EINVAL;
		return -1;
	}

	t->x.pid = pid;

#ifdef	BOUNDS
	checkbounds(t, "pid_set");
#endif	/* BOUNDS */

	STATUS("pid_set");
	UNLOCK();
	return 0;
}

int shm_pid_free(pid_t pid FILE_LINE_ARGS)
{
	shm_node_t *curr;
	FUN("shm_pid_free");

	LOGS(L_SHM,L_DEBUGX,("shm_pid_free(%u)%s\n",
		(uint32_t)pid, AT_FILE_LINE));
	if (0 != LOCK()) {
		LOGS(L_SHM,L_DEBUG,("lock failed%s\n",
			AT_FILE_LINE));
		errno = EINVAL;
		return -1;
	}

	curr = (shm_node_t *)g_shm->allocated;
	while (NULL != curr) {
		if (pid == curr->x.pid) {
#if	SHM_DEBUG
			LOGS(L_SHM,L_DEBUG,("freeing %p%s\n", curr,
				at_file_line(curr->x.file, curr->x.line)));
#else
			LOGS(L_SHM,L_DEBUG,("freeing %p\n", curr));
#endif
			delete(ALLOCATED, curr);
			curr->x.pid = getpid();
#if	SHM_DEBUG
			curr->x.file = file;
			curr->x.line = line;
#endif
			insert(AVAILABLE, curr);
		}
		curr = curr->x.next;
	}

	STATUS("pid_free");
	UNLOCK();
	return 0;
}

/* ARGUSED */
int shm_stats(shm_pool_stats_t *stats FILE_LINE_ARGS)
{
	size_t seg;
	FUN("shm_stats");

	LOGS(L_SHM,L_DEBUGX,("shm_stats(%p)%s\n",
		stats, AT_FILE_LINE));

	if (NULL == stats) {
#if	SHM_DEBUG
		if (NULL != file && 0 != line)
			debug();
#endif
		errno = EINVAL;
		return -1;
	}
	if (0 != LOCK()) {
		LOGS(L_SHM,L_DEBUG,("lock failed%s\n",
			AT_FILE_LINE));
		errno = EINVAL;
		return -1;
	}
	stats->total = 0;
	stats->used = 0;
	stats->free = 0;
	stats->allocated = g_shm->alloc_len;
	stats->available = g_shm->avail_len;
	for (seg = 0; seg < g_shm->pool_cnt; seg++) {
		stats->total += g_shm->max[seg];
		stats->used += g_shm->brk[seg];
		stats->free += g_shm->max[seg] - g_shm->brk[seg];
	}
	UNLOCK();
	return 0;
}	/* shm_stats */

void shm_pool_exit(void)
{
	FUN("shm_pool_exit");
#if	HAVE_MMAP
	if (NULL != g_shm && MAP_FAILED != (caddr_t)g_shm) {
		osd_sem_destroy(&g_shm->sem);
#if	USE_SVID_SEMAPHORES || USE_FLOCK_SEMAPHORES
		osd_sem_global_destroy(&g_shm->semglobals);
#endif	/* USE_SVID_SEMAPHORES || USE_FLOCK_SEMAPHORES */
		munmap((caddr_t)g_shm, sizeof(shm_pool_t));
		g_shm = NULL;
	}
#else
	if (NULL != g_shm && -1 != (int)g_shm) {
		size_t i;
		osd_sem_destroy(&g_shm->sem);
		for (i = 0; i < SHM_POOLSEGS; i++) {
			if (NULL != g_shm->pool[i] &&
				-1 != (int)g_shm->pool[i]) {
				shmdt(g_shm->pool[i]);
				g_shm->pool[i] = NULL;
			}
			if (0 != g_shm->shmid[i] && -1 != g_shm->shmid[i]) {
				shmctl(g_shm->shmid[i], IPC_RMID, NULL);
				g_shm->shmid[i] = -1;
				g_shm->key[i] = -1;
			}
		}
		shmdt(g_shm);
		g_shm = NULL;
		if (0 != g_shm_id && -1 != g_shm_id) {
			shmctl(g_shm_id, IPC_RMID, NULL);
			g_shm_id = -1;
		}
		g_shm_key = -1;
	}
#endif
}

int shm_pool(char **argv)
{
	size_t seg, size;
	int flags;
	int rc;
	configuration_t *s_conf;
	FUN("shm_pool");

#if	HAVE_MMAP
	(void)argv;
	/******************************************
	 * implement shared memory with mmap()
	 ******************************************/
	size = sizeof(shm_pool_t) + SHM_POOLSIZE;
	flags = MAP_ANON | MAP_SHARED;
#ifdef	MAP_HASSEMAPHORE
	flags |= MAP_HASSEMAPHORE;
#endif
	g_shm = (shm_pool_t *)mmap(NULL, size, PROT_READ | PROT_WRITE, flags, -1, 0);
	if (NULL == g_shm || MAP_FAILED == (caddr_t)g_shm) {
		fprintf(stderr, "failed to mmap() shm_pool size %#llx (%s)\n",
			(uint64_t)size, strerror(errno));
		return -1;
	}
	memset(g_shm, 0, size);
	size = SHM_POOLSIZE / SHM_POOLSEGS;
	for (seg = 0; seg < SHM_POOLSEGS; seg++) {
		g_shm->pool[seg] = &g_shm->data[seg * size];
		g_shm->max[seg] = size;
	}
	g_shm->pool_cnt = SHM_POOLSEGS;
#else
	/******************************************
	 * implement shared memory with SysV shm
	 ******************************************/
	size = sizeof(shm_pool_t);
	g_shm_key = ftok(argv[0], 1 + SHM_POOLSEGS);
	flags = IPC_CREAT | SHM_R | SHM_W | (SHM_R >> 3) | (SHM_W >> 3);
	g_shm_id = shmget(g_shm_key, size, flags);
	if (-1 == g_shm_id) {
		fprintf(stderr, "shmget(%#x, %d, 0%o) call failed (%s)\n",
			g_shm_key, (int)size, flags, strerror(errno));
		return -1;
	}
	g_shm = shmat(g_shm_id, NULL, 0);
	if (-1 == (int)g_shm) {
		fprintf(stderr, "shmat(%#x, NULL, 0) call failed (%s)\n",
			g_shm_id, strerror(errno));
		return -1;
	}
	fprintf(stdout, "shmat() for shm_pool (size %x) return 0x%x\n",
		size, (unsigned)g_shm);
	memset(g_shm, 0, size);
	for (seg = 0; seg < SHM_POOLSEGS; seg++) {
		g_shm->key[seg] = ftok(argv[0], 1 + seg);
		size = SHMMAX;
		g_shm->shmid[seg] = shmget(g_shm->key[seg], size, flags);
		if (-1 == g_shm->shmid[seg]) {
			fprintf(stderr, "shmget(%#x, %d, %d) call failed (%s)\n",
				g_shm->key[seg], (int)size, flags, strerror(errno));
			return -1;
		}
		g_shm->pool[seg] = shmat(g_shm->shmid[seg], NULL, 0);
		if (-1 == (int)g_shm->pool[seg]) {
			fprintf(stderr, "shmat(%#x, NULL, 0) call failed (%s)\n",
				g_shm->shmid[seg], strerror(errno));
			return -1;
		}
		g_shm->max[seg] = size;
	}
	g_shm->pool_cnt = SHM_POOLSEGS;
#endif

#if	USE_SVID_SEMAPHORES || USE_FLOCK_SEMAPHORES
	if (0 != (rc = osd_sem_global_init(&g_shm->semglobals))) {
		LOG(L_ERROR,("osd_sem_global_init(%p) call failed (%s)\n",
			&g_shm->semglobals, strerror(errno)));
		return -1;
	}
#endif	/* USE_SVID_SEMAPHORES || USE_FLOCK_SEMAPHORES */

	if (0 != (rc = osd_sem_init(&g_shm->sem, 1, 1))) {
		LOGS(L_SHM,L_ERROR,("osd_sem_init(%p,%d,%d) call failed (%s)\n",
			&g_shm->sem, 1, 1, strerror(errno)));
		return -1;
	}

	/* Move g_conf into SHM, now that it is initialized. */
	s_conf = (configuration_t *)scalloc(1, sizeof(configuration_t));
	memcpy(s_conf, g_conf, sizeof(configuration_t));
	xfree(g_conf);
	g_conf = s_conf;

	return 0;
}
